# 1001
def b_1001():
    n = int(input())
    count = 0
    while n != 1:
        if n % 2 == 0:
            n /= 2
        else:
            n = (3 * n + 1) / 2
        count += 1
    print(count)


# 1002
def b_1002():
    word = ['ling', 'yi', 'er', 'san', 'si', 'wu', 'liu', 'qi', 'ba', 'jiu']
    n = input()
    sum_n = 0
    for i in range(len(n)):
        sum_n += int(n[i])
    str_n = str(sum_n)
    result = ''
    for j in range(len(str_n)):
        result = result + word[int(str_n[j])] + ' '
    result = result[0:(len(result)-1)]
    print(result)


# 1003
def b_1003():
    import re
    n = input()
    end_ = '\n'
    for i in range(int(n)):
        s = input()
        reg1 = r"[PAT\x20]"
        reg2 = r"([A\x20])*PA+T([A\x20])*$"
        m = (re.match(reg1, s) is not None) and (re.match(reg2, s) is not None)
        if i == int(n) - 1:
            end_ = ''
        if m is True:
            part1 = s.split('P')[0]
            part2 = s.split('T')[1]
            part3 = s.split('P')[1].split('T')[0]
            if len(part1) * len(part3) == len(part2):
                print('YES', end=end_)
            else:
                print('NO', end=end_)
        else:
            print('NO', end=end_)


# 1004
def b_1004():
    len_ = int(input())
    class_list = {}
    grade_list = {}
    for i in range(len_):
        str_ = input().split(' ')
        class_list.update({str_[1]: str_[0]})
        grade_list.update({str_[1]: str_[2]})
    max_ = -1
    min_ = 101
    max_id = ''
    min_id = ''
    for i in grade_list.keys():
        if int(grade_list.get(i)) > max_:
            max_id = i
            max_ = int(grade_list.get(i))
        if int(grade_list.get(i)) < min_:
            min_id = i
            min_ = int(grade_list.get(i))
    print(str(class_list.get(max_id)) + ' ' + max_id)
    print(str(class_list.get(min_id)) + ' ' + min_id)


# 1005
def b_1005():
    n = int(input())
    number = input().split(' ')
    box = {}
    for i in range(1, 100):
        box.update({101-i: -1})
    for i in range(n):
        t = int(number[i])
        if int(box.get(t)) == -1:
            box.update({t: 0})
        while t != 2:
            if t % 2 == 0:
                t /= 2
            else:
                t = (3 * t + 1) / 2
            box.update({t: 1})
    s = ''
    for k in box.keys():
        if int(box.get(k)) == 0:
            s += str(k) + ' '
    print(s[:len(s)-1])


# 1006
def b_1006():
    number = input()
    out = ''
    if len(number) >= 1:
        g = int(number) % 10
        for i in range(g):
            out = out + str(i+1)
    if len(number) >= 2:
        s = int(int(number) % 100 / 10)
        for i in range(s):
            out = 'S' + out
    if len(number) >=3:
        b = int(int(number) / 100)
        for i in range(b):
            out = 'B' + out
    print(out)


# 1007
def b_1007():
    def is_prime(i):
        for j in range(2, int(i ** 0.5 + 1)):
            if i % j == 0:
                return False
        return True
    n = int(input())
    count = 0
    this = True
    for i in range(1, int((n-1) / 2)):
        if i+2 <= n:
            if this is True:
                if is_prime(i * 2 + 3):
                    count += 1
                    this = True
                else:
                    this = False
            else:
                if is_prime(i * 2 + 3):
                    this = True
    print(count)


# 1008
def b_1008():
    s1 = input().split()
    n = int(s1[0])
    m = int(s1[1]) % n
    s2 = input().split()
    out = s2[-m:]
    out.extend(s2[0:-m])
    result = ''
    for i in range(len(out)):
        result = result + out[i] + ' '
    print(result[:-1])


# 1009
def b_1009():
    s = input().split(' ')
    t = ''
    for i in range(len(s)):
        t = s[i] + ' ' + t
    print(t[:-1])


# 1010
def b_1010():
    s = input().split()
    out = ''
    for i in range(len(s)):
        if i % 2 == 0:
            a = int(s[i])
            e = int(s[i+1])
            if e == 0 and a != 0:
                continue
            elif e == 0:
                e += 1
            a = a * e
            e = e - 1
            out = out + str(a) + ' ' + str(e) + ' '
    if len(s) == 0:
        out = '0 0 '
    if len(s) == 2 and int(s[1]) == 0:
        out = '0 0 '
    print(out[:-1], end='')


# 1011
def b_1011():
    l = int(input())
    for i in range(l):
        a, b, c = input().split(' ')
        a = int(a)
        b = int(b)
        c = int(c)
        if a + b > c:
            print('Case #' + str(i+1) + ': true')
        else:
            print('Case #' + str(i+1) + ': false')


# 1012
def b_1012():
    s = input().split(' ')
    n = int(s[0])
    s = s[1:]
    a1 = 0
    count1 = 0
    a2 = 0
    count2 = 0
    a3 = 0
    count3 = 0
    a4 = 0
    count4 = 0
    a5 = 0
    count5 = 0
    for i in range(n):
        if int(s[i]) % 10 == 0:
            a1 += int(s[i])
            count1 += 1
        elif int(s[i]) % 5 == 1:
            a2 = a2 + ((-1) ** count2) * int(s[i])
            count2 += 1
        elif int(s[i]) % 5 == 2:
            a3 += 1
            count3 += 1
        elif int(s[i]) % 5 == 3:
            a4 += int(s[i])
            count4 += 1
        elif int(s[i]) % 5 == 4:
            if int(s[i]) > a5:
                a5 = int(s[i])
            count5 += 1
    if count1 == 0:
        a1 = 'N'
    if count2 == 0:
        a2 = 'N'
    if count3 == 0:
        a3 = 'N'
    if count4 == 0:
        a4 = 'N'
    else:
        a4 = a4 / count4
        if a4 != int(a4):
            a4 = round(a4, 1)
        else:
            a4 = int(a4)
    if count5 == 0:
        a5 = 'N'
    print(str(a1) + ' ' + str(a2) + ' ' + str(a3) + ' ' + str(a4) + ' ' + str(a5))


# 1013
def b_1013():
    def is_prime(i):
        for j in range(2, int(i ** 0.5 + 1)):
            if i % j == 0:
                return False
        return True
    m, n = input().split(' ')
    m = int(m)
    n = int(n)
    a = 2
    count = 0
    c = 0
    s = ''
    while count <= n:
        if is_prime(a):
            count += 1
            if m <= count <= n:
                s = s + str(a)
                c += 1
                if c % 10 == 0:
                    s = s + '\n'
                else:
                    s = s + ' '
        if a == 2:
            a = 3
        else:
            a += 2
    print(s[:-1])


# 1014
def b_1014():
    s1 = input()
    s2 = input()
    s3 = input()
    s4 = input()
    week = ['MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT', 'SUN']
    day = 'ABCDEFG'
    hour = '0123456789ABCDEFGHIJKLMN'
    minute = '0'
    len1 = len(s1)
    if len1 >= len(s2):
        len1 = len(s2)
    len2 = len(s3)
    if len2 >= len(s4):
        len2 = len(s4)
    count = 1
    for i in range(len1):
        if s1[i] == s2[i] and count == 1 and day.find(s1[i]) != -1:
            day = week[day.index(s1[i])]
            count = 2
        elif s1[i] == s2[i] and count == 2 and hour.find(s1[i]) != -1:
            hour = '0' + str(hour.index(s1[i]))
            count = 3
            break
    for i in range(len2):
        if s3[i] == s4[i] and count == 3 and s3[i].isalpha():
            minute = minute + str(i)
    if len(hour) == 3:
        hour = hour[1:]
    if len(minute) == 3:
        minute = minute[1:]
    result = day + ' ' + hour + ':' + minute
    print(result, end='')
    return 0


# 1015 性能题（字典代替转换，sys代替in/output，减少append等操作)
def b_1015():
    import sys
    class student:
        def __init__(self, id_, de, cai):
            self.id_ = id_
            self.de = de
            self.cai = cai
            self.sum = de + cai

    def main():
        n, l, h = sys.stdin.readline().split()
        score_dict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,
                      '10': 10, '11': 11, '12': 12, '13': 13, '14': 14, '15': 15, '16': 16, '17': 17,
                      '18': 18, '19': 19, '20': 20, '21': 21, '22': 22, '23': 23, '24': 24, '25': 25,
                      '26': 26, '27': 27, '28': 28, '29': 29, '30': 30, '31': 31, '32': 32, '33': 33,
                      '34': 34, '35': 35, '36': 36, '37': 37, '38': 38, '39': 39, '40': 40, '41': 41,
                      '42': 42, '43': 43, '44': 44, '45': 45, '46': 46, '47': 47, '48': 48, '49': 49,
                      '50': 50, '51': 51, '52': 52, '53': 53, '54': 54, '55': 55, '56': 56, '57': 57,
                      '58': 58, '59': 59, '60': 60, '61': 61, '62': 62, '63': 63, '64': 64, '65': 65,
                      '66': 66, '67': 67, '68': 68, '69': 69, '70': 70, '71': 71, '72': 72, '73': 73,
                      '74': 74, '75': 75, '76': 76, '77': 77, '78': 78, '79': 79, '80': 80, '81': 81,
                      '82': 82, '83': 83, '84': 84, '85': 85, '86': 86, '87': 87, '88': 88, '89': 89,
                      '90': 90, '91': 91, '92': 92, '93': 93, '94': 94, '95': 95, '96': 96, '97': 97,
                      '98': 98, '99': 99, '100': 100}
        info = {}
        n = int(n)
        l = score_dict[l]
        h = score_dict[h]
        stus1 = []
        stus2 = []
        stus3 = []
        stus4 = []
        for i in range(n):
            iii = sys.stdin.readline()
            id__, de_, cai_ = iii.split()
            de_ = score_dict[de_]
            cai_ = score_dict[cai_]
            id__ = int(id__)
            stu = student(id__, de_, cai_)
            if de_ >= h and cai_ >= h:
                stus1.append(stu)
                info[id__] = iii
            elif de_ >= h > cai_ >= l:
                stus2.append(stu)
                info[id__] = iii
            elif h > de_ >= cai_ >= l:
                stus3.append(stu)
                info[id__] = iii
            elif de_ >= l and cai_ >= l:
                stus4.append(stu)
                info[id__] = iii

        stus1.sort(reverse=True, key=lambda st: (st.sum, st.de, -st.id_))
        stus2.sort(reverse=True, key=lambda st: (st.sum, st.de, -st.id_))
        stus3.sort(reverse=True, key=lambda st: (st.sum, st.de, -st.id_))
        stus4.sort(reverse=True, key=lambda st: (st.sum, st.de, -st.id_))

        print((len(stus1)+len(stus2)+len(stus3)+len(stus4)))
        for s in stus1:
            sys.stdout.write(info[s.id_])
        for s in stus2:
            sys.stdout.write(info[s.id_])
        for s in stus3:
            sys.stdout.write(info[s.id_])
        for s in stus4:
            sys.stdout.write(info[s.id_])

    main()


# 1016
def b_1016():
    import sys

    def main():
        a, da, b, db = sys.stdin.readline().split()
        pa = ''
        pb = ''
        for i in a:
            if i == da:
                pa += da
        for i in b:
            if i == db:
                pb += db
        if pa == '':
            pa = 0
        else:
            pa = int(pa)
        if pb == '':
            pb = 0
        else:
            pb = int(pb)
        print((pa+pb))

    main()


# 1017
def b_1017():
    import sys

    def main():
        a, b = sys.stdin.readline().split()
        b = int(b)
        c = int(a[0])
        ans = ''
        if len(a) != 1:
            for i in range(0, len(a)):
                cc = c
                if int(cc/b) > 0:
                    temp = int(cc/b)
                    ans = ans+str(temp)
                    c = cc % b
                    if i != len(a)-1:
                        c = c * 10 + int(a[i+1])
                else:
                    ans = ans+str(0)
                    if i != len(a)-1:
                        c = c * 10 + int(a[i+1])
        else:
            ans = str(int(c/b))
            c = c % b
        if ans == '0':
            c = c
        elif ans[0] == '0':
            ans = ans[1:]
        print(ans+' '+str(c))

    main()


# 1018
def b_1018():
    import sys
    n = int(input())
    a_win = 0
    a_lose = 0
    a_b = 0
    a_s = {'C': 0, 'B': 0, 'J': 0}
    b_s = {'C': 0, 'B': 0, 'J': 0}
    for i in range(n):
        a, b = sys.stdin.readline().split()
        if (a == 'C' and b == 'J') or (a == 'J' and b == 'B') or (a == 'B' and b == 'C'):
            a_win += 1
            a_s[a] += 1
        elif (a == 'C' and b == 'B') or (a == 'J' and b == 'C') or (a == 'B' and b == 'J'):
            a_lose += 1
            b_s[b] += 1
        else:
            a_b += 1
    a_most = 'B'
    b_most = 'B'
    for i in a_s.keys():
        if (a_s[i] > a_s[a_most]) or (a_s[i] == a_s[a_most] and i < a_most):
            a_most = i
    for i in b_s.keys():
        if (b_s[i] > b_s[b_most]) or (b_s[i] == b_s[b_most] and i < b_most):
            b_most = i
    sys.stdout.write(str(a_win)+' '+str(a_b)+' '+str(a_lose)+'\n')
    sys.stdout.write(str(a_lose) + ' ' + str(a_b) + ' ' + str(a_win)+'\n')
    sys.stdout.write(a_most + ' ' + b_most+'\n')


# 1019
def b_1019():
    def sort(s):
        ss = [s[0], s[1], s[2], s[3]]
        ss.sort()
        f = ss[0]+ss[1]+ss[2]+ss[3]
        z = ss[3]+ss[2]+ss[1]+ss[0]
        return z, f
    n = input()
    n = '0000'+n
    n = n[-4:]
    while True:
        z_, f_ = sort(n)
        z__ = int(z_)
        f__ = int(f_)
        n = z__ - f__
        if n == 0:
            n = '0000'
            print(z_ + ' - ' + f_ + ' = ' + n)
            break
        elif n == 6174:
            n = '6174'
            print(z_ + ' - ' + f_ + ' = ' + n)
            break
        elif n < 1000:
            n = '0' + str(n)
            print(z_ + ' - ' + f_ + ' = ' + str(n))
        else:
            n = str(n)
            print(z_+' - '+f_+' = '+n)


# b_1020(正数和正整数要看清楚）
def b_1020():
    import sys
    class yb:
        def __init__(self, kc, zj):
            self.kc = kc
            self.zj = zj
            self.dj = zj / kc

    def main():
        n, d = input().split()
        n = int(n)
        d = int(d)
        ybs = []
        ks = sys.stdin.readline().split()
        zs = sys.stdin.readline().split()
        for i in range(n):
            k, z = ks[i], zs[i]
            k = float(k)
            z = float(z)
            yb_ = yb(k, z)
            ybs.append(yb_)
        ybs.sort(reverse=True, key=lambda x: (x.dj, x.kc))
        yb_i = 0
        sy = 0
        while True:
            if yb_i >= n:
                break
            if d <= ybs[yb_i].kc:
                sy = sy + d * ybs[yb_i].dj
                break
            else:
                d = d - ybs[yb_i].kc
                sy = sy + ybs[yb_i].zj
                yb_i += 1
        print('%.2f' % sy)

    main()


# b_1021
def b_1021():
    dic = dict(zip([str(i) for i in range(10)], [0 for _ in range(10)]))
    s = input()
    for i in s:
        dic[i] += 1
    for i in dic.keys():
        if dic[i] != 0:
            print(i+':'+str(dic[i]))


# b_1022
def b_1022():
    num_dict = dict(zip([str(i) for i in range(11)], range(11)))
    str_dict = dict(zip(range(11), [str(i) for i in range(11)]))

    def change(s, j):
        num = int(s)
        res = ''
        while True:
            if num < j:
                res = str_dict[num] + res
                break
            temp_ = num % j
            num = num // j
            res = str_dict[temp_] + res
        return res
    a, b, d = input().split(' ')
    d = num_dict[d]
    if len(a) < len(b):
        temp = a
        a = b
        b = temp
    l_max = len(a)
    l_min = len(b)
    sum_ = ''
    c = 0
    for i in range(l_min):
        x = num_dict[a[-(i+1)]]
        y = num_dict[b[-(i+1)]]
        temp = (x + y + c) % 10
        c = (x + y + c) // 10
        sum_ = str_dict[temp] + sum_
    for i in range(l_max - l_min):
        x = num_dict[a[-(l_min+i+1)]]
        temp = (x + c) % 10
        c = (x + c) // 10
        sum_ = str_dict[temp] + sum_
    if c == 1:
        sum_ = str_dict[c] + sum_
    result = change(sum_, d)
    print(result)


# b_1023
def b_1023():
    num_dict = dict(zip([str(i) for i in range(10)], range(10)))
    n = input().split()
    for i in range(len(n)):
        num_dict[str(i)] = int(n[i])
    num = []
    for i in range(10):
        for j in range(num_dict[str(i)]):
            num.append(str(i))
    num.sort()
    f = False
    for i in range(len(num)):
        if num[i] == '0':
            f = True
        if num[i] != '0' and f is True:
            num[0] = num[i]
            num[i] = '0'
            break
    str_ = ''
    for i in range(len(num)):
        str_ = str_ + num[i]
    print(str_)


# b_1024
def b_1024():
    s = input()
    fh = s[0] if s[0] == '-' else ''
    bt = s[1:s.find('E')]
    mi = int(s[s.find('E')+1:])
    l = len(bt)
    if mi > 0:
        for i in range(mi - l + 2):
            bt = bt + '0'
        x = bt[0]
        for i in range(2, mi + 2):
            x = x + bt[i]
        x = x + '.'
        for i in range(mi + 2, len(bt)):
            x = x + bt[i]
        if x[-1] == '.':
            x = x[:-1]
    elif mi < 0:
        for i in range(abs(mi)):
            bt = '0' + bt
        x = bt[0] + '.' + bt[1:abs(mi)+1] + bt[abs(mi)+2:]
    else:
        x = bt
    result = fh + x
    print(result)


# b_1025
def b_1025():
    import sys

    def main():
        start, n, k = input().split()
        n = int(n)
        k = int(k)
        chain_dic = {}
        data_dic = {}
        for i in range(n):
            add, data, nex = sys.stdin.readline().split()
            data_dic[add] = data
            chain_dic[add] = nex
        chain = [start]
        while True:
            now = chain[-1]
            if chain_dic[now] == '-1':
                break
            else:
                chain.append((chain_dic[now]))
        temp = []
        result = []
        count = 1
        for i in chain:
            if count == k:
                temp.append(i)
                temp.reverse()
                result.extend(temp)
                count = 1
                temp = []
            else:
                temp.append(i)
                count += 1
        if count != 1:
            result.extend(chain[(-count+1):])
        for i in range(len(result)-1):
            chain_dic[result[i]] = result[i+1]
        chain_dic[result[-1]] = '-1'
        for i in result:
            print(i+' '+data_dic[i]+' '+chain_dic[i])

    main()


# b_1026
def b_1026():
    c1, c2 = input().split()
    c1 = int(c1)
    c2 = int(c2)
    c = (c2 - c1) / 100
    h = c // 3600
    m = (c - 3600 * h) // 60
    s = int(c - 3600 * h - 60 * m + 0.5)
    if s == 60:
        s = 0
        m += 1
    if m == 60:
        m = 0
        h += 1
    s = '0' + str(int(s))
    m = '0' + str(int(m))
    h = '0' + str(int(h))
    s = s[-2:]
    m = m[-2:]
    h = h[-2:]
    print(h+':'+m+':'+s)


# b_1027
def b_1027():
    n, f = input().split()
    n = int(n)
    layer = int(((n + 1) / 2) ** 0.5)
    noko = n - (layer ** 2) * 2 + 1
    for i in range(layer):
        s = ''
        for j in range(i):
            s = s + ' '
        for j in range(2 * (layer - i) - 1):
            s = s + f
        print(s)
    for i in range(1, layer):
        s = ''
        for j in range(layer - i - 1):
            s = s + ' '
        for j in range(i * 2 + 1):
            s = s + f
        print(s)
    print(noko)


# b_1028
def b_1028():
    import sys

    def main():
        n = int(input())
        bs = []
        s_dict = {}
        count = 0
        for i in range(n):
            name, birth = sys.stdin.readline().split()
            if '2014/09/06' >= birth >= '1814/09/06':
                s_dict[birth] = name
                bs.append(birth)
                count += 1
        bs.sort()
        if count != 0:
            print(str(count) + ' ' + s_dict[bs[0]] + ' ' + s_dict[bs[-1]])
        else:
            print(str(count))
    main()


# b_1029
def b_1029():
    a = ''
    b = {'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 0, 'L': 0
         , 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0, 'S': 0, 'T': 0, 'U': 0, 'V': 0, 'W': 0, 'X': 0
         , 'Y': 0, 'Z': 0, 'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0
         , 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0
         , 'w': 0, 'x': 0, 'y': 0, 'z': 0, '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0
         , '6': 0, '7': 0, '8': 0, '9': 0, '_': 0}
    good = input()
    bad = input()
    for i in bad:
        b[i] = 1
    for i in good:
        if b[i] == 0:
            a += i if i.isupper() else i.upper()
    d = ''
    for i in a:
        if d.find(i) == -1:
            d = d + i
    print(d)


# b_1030
def b_1030():
    import sys

    def main():
        n, p = sys.stdin.readline().split()
        p = int(p)
        s = sys.stdin.readline().split()
        n = int(n)
        s = [int(s[i]) for i in range(n)]
        s.sort()
        start = 0
        end = 1
        max_len = 0
        while True:
            if n - start <= max_len or start == n or end >= n:
                break
            if s[start] * p >= s[end]:
                end += 1
            else:
                len_ = end - start
                if len_ > max_len:
                    max_len = len_
                start += 1
                end = start + max_len
        if end - start > max_len:
            max_len = end - start
        sys.stdout.write(str(max_len)+'\n')
    main()


# b_1031
def b_1031():
    import sys
    num_dict = dict(zip([str(i) for i in range(10)], range(10)))
    num_dict['X'] = 10
    zm_dict = {0: 1, 1: 0, 2: 10, 3: 9, 4: 8, 5: 7, 6: 6, 7: 5, 8: 4, 9: 3, 10: 2}
    w = [7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2]

    def pd(s):
        if len(s) != 19:
            return False
        sum_ = 0
        for i in range(len(s)-2):
            if s[i].isdigit() is False:
                return False
            sum_ = sum_ + num_dict[s[i]] * w[i]
        if zm_dict[sum_ % 11] == num_dict[s[-2]]:
            return True
        else:
            return False

    def main():
        n = int(input())
        wxsfz = []
        for i in range(n):
            sfz = sys.stdin.readline()
            if pd(sfz) is False:
                wxsfz.append(sfz)
        if len(wxsfz) == 0:
            print('All passed')
        else:
            for i in wxsfz:
                print(i, end='')
    main()


# b_1032
def b_1032():
    import sys

    def main():
        score_dict = dict(zip([str(i) for i in range(101)], range(101)))
        n = int(input())
        s = {}
        max_s = 0
        max_ = ''
        for i in range(n):
            u_id, u_sum = sys.stdin.readline().split()
            u_sum = score_dict[u_sum]
            if u_id not in s.keys():
                s[u_id] = u_sum
            else:
                s[u_id] += u_sum
            if max_ == '':
                max_ = u_id
                max_s = u_sum
            else:
                if s[u_id] > max_s:
                    max_ = u_id
                    max_s = s[u_id]

        print(max_+' '+str(max_s))
    main()


# b_1033
def b_1033():
    s1 = input()
    s2 = input()
    res = ''
    for i in s2:
        if (i not in s1) and not ('+' in s1 and i.isupper()) and (i.upper() not in s1):
            res = res + i
    print(res)


# b_1034
def b_1034():
    num1, num2 = input().split()

    def gys(x, y):
        if x < y:
            x, y = y, x  # 保证a大于b
        while x % y != 0:
            x, y = y, x % y
        return y

    def muti(n1, n2):
        f1, f2 = 1, 1
        if n1[0] == '-':
            f1 = -1
            n1 = n1[1:]
        if n2[0] == '-':
            f2 = -1
            n2 = n2[1:]
        pos1, pos2 = n1.find('/'), n2.find('/')
        a1, a2, b1, b2 = int(n1[:pos1]), int(n2[:pos2]), int(n1[pos1+1:]), int(n2[pos2+1:])
        a3 = a1 * a2
        b3 = b1 * b2
        f = f1 * f2
        if f == -1:
            res = '-' + str(a3) + '/' + str(b3)
        else:
            res = str(a3) + '/' + str(b3)
        return res

    def add(n1, n2):
        f1, f2 = 1, 1
        if n1[0] == '-':
            f1 = -1
            n1 = n1[1:]
        if n2[0] == '-':
            f2 = -1
            n2 = n2[1:]
        pos1, pos2 = n1.find('/'), n2.find('/')
        a1, a2, b1, b2 = int(n1[:pos1]), int(n2[:pos2]), int(n1[pos1 + 1:]), int(n2[pos2 + 1:])
        t = gys(b1, b2)
        t1, t2 = b2 // t, b1 // t
        a3 = a1 * t1 * f1 + a2 * t2 * f2
        b3 = (b1 * b2) // t
        res = str(a3) + '/' + str(b3)
        return res

    def sub(n1, n2):
        if n2[0] == '-':
            n2 = n2[1:]
        else:
            n2 = '-' + n2
        return add(n1, n2)

    def dev(n1, n2):
        res = ''
        if n2[0] == '-':
            res = '-'
            n2 = n2[1:]
        pos_ = n2.find('/')
        a, b = n2[:pos_], n2[pos_+1:]
        res = res + b + '/' + a
        return muti(n1, res)

    def change(s):
        res = ''
        f = 1
        if s[0] == '-':
            res = '(-'
            s = s[1:]
            f = -1
        pos = s.find('/')
        a = int(s[:pos])
        b = int(s[pos+1:])
        if b == 0:
            return 'Inf'
        zs = a // b
        fz = a % b

        if fz == 0 and zs == 0:
            return '0'
        elif fz == 0 and zs != 0:
            res = res + str(zs)
        elif fz != 0 and zs == 0:
            t = gys(fz, b)
            fz = fz // t
            b = b // t
            res = res + str(fz) + '/' + str(b)
        else:
            t = gys(fz, b)
            fz = fz // t
            b = b // t
            res = res + str(zs) + ' '+str(fz) + '/' + str(b)
        if f == -1:
            res = res + ')'
        return res

    num1_ = change(num1)
    num2_ = change(num2)
    print(num1_ + ' + ' + num2_ + ' = ' + change(add(num1, num2)))
    print(num1_ + ' - ' + num2_ + ' = ' + change(sub(num1, num2)))
    print(num1_ + ' * ' + num2_ + ' = ' + change(muti(num1, num2)))
    print(num1_ + ' / ' + num2_ + ' = ' + change(dev(num1, num2)))


# b_1035
def b_1035():
    def MergeSort(lists, num):
        if len(lists) <= num:
            lists.sort()
            return lists
        else:
            over = lists[:num]
            over.sort()
            po = num
            for i in range(num, len(lists)-num, num):
                if i+num < len(lists):
                    temp = lists[i: i+num]
                    po = i + num
                else:
                    temp = lists[i: len(lists)]
                    po = len(lists)
                temp.sort()
                over.extend(temp)
            if po != len(lists):
                temp = lists[po: len(lists)]
                temp.sort()
                over.extend(temp)
            return over

    def main():
        n = int(input())
        s = input().split()
        x = input().split()
        z = []
        for i in x:
            z.append(int(i))
        f = 'Insertion Sort'
        pos = 0
        for i in range(1, n):
            if z[i] >= z[i-1]:
                pos = i
            else:
                break
        for i in range(pos+1, n):
            if z[i] != int(s[i]):
                f = 'Merge Sort'
                break
        if f == 'Insertion Sort':
            ins = z[pos+1]
            ppp = pos
            for i in range(pos, -1, -1):
                if z[i] > ins:
                    z[i+1] = z[i]
                    ppp = i
                else:
                    z[i+1] = str(ins)
                    break
            if ppp == 0:
                z[0] = str(ins)
        else:
            dd = 0
            for i in range(len(z)-1):
                if z[i+1] >= z[i]:
                    dd += 1
                else:
                    if dd < pos:
                        pos = dd
                    dd = 0
            pos = (pos + 1) * 2
            z = MergeSort(z, pos)
        print(f)
        sss = ''
        for i in z:
            sss = sss + str(i) + ' '
        print(sss[:-1])

    main()


# b_1036
def b_1036():
    n, f = input().split()
    n = int(n)
    h = int(n / 2 + 0.5)
    s = ''
    for i in range(n):
        s = s+f
    x = f
    for i in range(n-2):
        x = x+' '
    x = x+f
    print(s)
    for i in range(h-2):
        print(x)
    print(s)


# b_1037
def b_1037():
    p, a = input().split()
    pg_, ps_, pk_ = p.split('.')
    ag_, as_, ak_ = a.split('.')
    pp = int(pg_) * 17 * 29 + int(ps_) * 29 + int(pk_)
    aa = int(ag_) * 17 * 29 + int(as_) * 29 + int(ak_)
    s = aa - pp
    t = ''
    if s < 0:
        t = '-'
        s = abs(s)
    sk_ = s % 29
    ss_ = ((s - sk_) // 29) % 17
    sg_ = s // (17 * 29)
    print(t+str(sg_)+'.'+str(ss_)+'.'+str(sk_))


# b_1038（性能题，网上只能找到唯一解，建议换个语言）
def b_1038():
    def main():
        n = int(input())
        st = input().split()
        cx = input().split()
        cx = cx[1:]
        print(' '.join([str(st.count(i)) for i in cx]))
    main()


# b_1039（列表不要直接对等，不然指向空间都是一样的）
def b_1039():
    def main():
        zz_disc = {'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 0, 'L': 0
         , 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0, 'S': 0, 'T': 0, 'U': 0, 'V': 0, 'W': 0, 'X': 0
         , 'Y': 0, 'Z': 0, 'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0
         , 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0
         , 'w': 0, 'x': 0, 'y': 0, 'z': 0, '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}
        dd_disc = {'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 0, 'L': 0
         , 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0, 'S': 0, 'T': 0, 'U': 0, 'V': 0, 'W': 0, 'X': 0
         , 'Y': 0, 'Z': 0, 'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0
         , 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0
         , 'w': 0, 'x': 0, 'y': 0, 'z': 0, '0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}
        s1 = input()
        s2 = input()
        duo = 0
        shao = 0
        for i in s1:
            zz_disc[i] += 1
        for i in s2:
            dd_disc[i] += 1
        for i in zz_disc.keys():
            z = zz_disc[i]
            d = dd_disc[i]
            if z > d:
                duo = duo + z - d
            elif d > z:
                shao = shao + d - z
        if shao > 0:
            print('No ' + str(shao))
        else:
            print('Yes ' + str(duo))

    main()


# b_1040
def b_1040():
    def main():
        s = input()
        p_a = {}
        a_t = {}
        p_num = 0
        t_num = 0
        num = 0
        for i in range(len(s)):
            if s[i] == 'P':
                p_num += 1
            elif s[i] == 'A':
                p_a[num] = p_num
                num += 1
        num -= 1
        for i in range(len(s)-1, -1, -1):
            if s[i] == 'T':
                t_num += 1
            elif s[i] == 'A':
                a_t[num] = t_num
                num -= 1
        sum_ = 0
        for i in p_a.keys():
            sum_ = (sum_ + p_a[i] * a_t[i]) % 1000000007
        print(sum_)
    main()


# b_1041
def b_1041():
    import sys
    def main():
        n = int(input())
        sj_dict = {}
        ks_dict = {}
        for i in range(n):
            zkz, sj, ks = sys.stdin.readline().split()
            sj_dict[sj] = zkz
            ks_dict[zkz] = ks
        m = int(input())
        mm = input().split()
        for i in mm:
            print(sj_dict[i] + ' ' + ks_dict[sj_dict[i]])

    main()


# b_1042
def b_1042():
    def main():
        s = input()
        s_dict = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0
         , 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0
         , 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
        for i in s:
            if i.isalpha():
                i = i.lower()
                s_dict[i] += 1
        max_ = 0
        alpha = ''
        for i in s_dict.keys():
            if s_dict[i] > max_:
                alpha = i
                max_ = s_dict[i]
        print(alpha+' '+str(max_))
    main()


# b_1043
def b_1043():
    def main():
        s_dict = {'P': 0, 'A': 0, 'T': 0, 'e': 0, 's': 0, 't': 0}
        s = input()
        for i in s:
            if i == 'P' or i == 'A' or i == 'T' or i == 'e' or i == 's' or i == 't':
                s_dict[i] += 1
        f = True
        ss = ''
        while f:
            f = False
            for i in 'PATest':
                if s_dict[i] != 0:
                    f = True
                    ss = ss + i
                    s_dict[i] -= 1
        print(ss)
    main()


# b_1044
def b_1044():
    import sys
    dig_dict_g = dict(zip(range(13), ['tret', 'jan', 'feb', 'mar', 'apr', 'may', 'jun', 'jly', 'aug', 'sep', 'oct', 'nov', 'dec']))
    dig_dict_s = dict(zip(range(13), ['', 'tam ', 'hel ', 'maa ', 'huh ', 'tou ', 'kes ', 'hei ', 'elo ', 'syy ', 'lok ', 'mer ', 'jou ']))
    mar_dict_g = dict(zip(['tret', 'jan', 'feb', 'mar', 'apr', 'may', 'jun', 'jly', 'aug', 'sep', 'oct', 'nov', 'dec'], range(13)))
    mar_dict_s = dict(zip(['', 'tam', 'hel', 'maa', 'huh', 'tou', 'kes', 'hei', 'elo', 'syy', 'lok', 'mer', 'jou'], range(13)))

    def dig_(d):
        d = int(d)
        ds = d // 13
        dg = d % 13
        if dg != 0 and ds != 0:
            ans = dig_dict_s[ds]+dig_dict_g[dg]
        elif dg == 0 and ds != 0:
            ans = dig_dict_s[ds]
            ans = ans[:-1]
        else:
            ans = dig_dict_g[dg]
        print(ans)

    def mar_(m):
        ms = 0
        mg = 0
        if ' ' in m:
            mm = m.split(' ')
            ms = mar_dict_s[mm[0]]
            mg = mar_dict_g[mm[1]]
        else:
            if m in mar_dict_g.keys():
                mg = mar_dict_g[m]
            else:
                ms = mar_dict_s[m]
        ans = str((ms * 13 + mg))
        print(ans)

    def main():
        n = int(input())
        for i in range(n):
            s = sys.stdin.readline().replace('\n', '')
            if s.isdigit():
                dig_(s)
            else:
                mar_(s)
    main()


# b_1045
def b_1045():
    def main():
        n = int(input())
        s = [int(i) for i in input().split()]
        ans = []
        max_ = 0
        for i in range(n):
            if s[i] > max_:
                ans.append(s[i])
                max_ = s[i]
            else:
                for j in range(len(ans)-1, -1, -1):
                    if ans[j] >= s[i]:
                        del ans[j]
                    else:
                        break
        print(len(ans))
        if len(ans) == 0:
            print('')
        else:
            ans = [str(i) for i in ans]
            print(' '.join(ans))
    main()


# b_1046
def b_1046():
    import sys

    def main():
        n = int(input())
        s_dict = dict(zip([str(i) for i in range(101)], range(101)))
        jhe, yhe = 0, 0
        for i in range(n):
            jhan, jhua, yhan, yhua = [s_dict[i] for i in sys.stdin.readline().split()]
            sum_han = jhan + yhan
            if jhua == sum_han and yhua != sum_han:
                yhe += 1
            elif yhua == sum_han and jhua != sum_han:
                jhe += 1
        print(jhe, end=' ')
        print(yhe, end='\n')
    main()


# b_1047
def b_1047():
    import sys
    def main():
        n = int(input())
        s_dict = dict(zip([str(i) for i in range(101)], range(101)))
        sc = {}
        for i in range(n):
            id_, score = sys.stdin.readline().split()
            id_ = id_[:id_.find('-')]
            if id_ not in sc.keys():
                sc[id_] = s_dict[score]
            else:
                sc[id_] += s_dict[score]
        max_ = 0
        max_id = ''
        for i in sc.keys():
            if sc[i] > max_:
                max_ = sc[i]
                max_id = i
        print(max_id, end=' ')
        print(max_)

    main()


# b_1048
def b_1048():
    def main():
        num_dict = dict(zip([str(i) for i in range(10)], range(10)))
        str_dict = dict(zip(range(10), [str(i) for i in range(10)]))
        str_dict[10] = 'J'
        str_dict[11] = 'Q'
        str_dict[12] = 'K'
        a, b = input().split()
        ans = ''
        l_a, l_b = len(a), len(b)
        if l_b < l_a:
            t = ''
            for i in range(l_a - l_b):
                t = t + '0'
            b = t + b
        l_b = len(b)
        for i in range(l_b):
            if i < l_a:
                pos_a = l_a - i - 1
                pos_b = l_b - i - 1
                if i % 2 == 0:
                    res = str_dict[((num_dict[a[pos_a]] + num_dict[b[pos_b]]) % 13)]
                else:
                    res = num_dict[b[pos_b]] - num_dict[a[pos_a]]
                    if res < 0:
                        res += 10
                    res = str_dict[res]
                ans = res + ans
            else:
                ans = b[l_b - i - 1] + ans
        print(ans)
    main()


# b_1049（精度不够大的时候，float换成Decimal，0就用Decimal(0)初始化）
def b_1049():
    from decimal import Decimal

    def main():
        n = int(input())
        num = [Decimal(i) for i in input().split(' ')]
        sum_ = Decimal(0)
        for i in range(n):
            sum_ = sum_ + (i + 1) * (n - i) * num[i]
        print('%.2f'%sum_)
    main()


# b_1050（这道题就是恶心人的，情况这么多，妈的）
def b_1050():
    def main():
        n = int(input())
        num = [int(i) for i in input().split()]
        num.sort(reverse=True)
        w, h = 1, 1
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                w = i
        h = n // w
        ans = [[0 for _ in range(w)] for _ in range(h)]
        x, y = 0, 0
        minx, miny, maxx, maxy = 0, 0, w-1, h-1
        for i in num:
            ans[y][x] = i
            if x == 0 and y == 0 and x < maxx:
                hx = 1
                zx = 0
            elif x == 0 and y == 0 and x == maxx and x == minx:
                hx = 0
                zx = 1
            elif minx < x < maxx and y == miny:
                hx = 1
                zx = 0
            elif x == maxx and y == miny:
                hx = 0
                zx = 1
                if maxx != w - 1:
                    minx += 1
            elif x == maxx and maxy > y > miny:
                hx = 0
                zx = 1
            elif x == maxx and y == maxy:
                hx = -1
                zx = 0
                miny += 1
            elif minx < x < maxx and y == maxy:
                hx = -1
                zx = 0
            elif x == minx and y == maxy:
                hx = 0
                zx = -1
                maxx -= 1
            elif x == minx and maxy > y > miny:
                hx = 0
                zx = -1
            else:
                hx = 1
                zx = 0
                maxy -= 1
            x = x + hx
            y = y + zx
        for i in ans:
            a = ''
            for j in i:
                a = a + str(j) + ' '
            print(a[:-1])
    main()


# b_1051（弱智题目，所谓的保留两位小数指的是直接舍掉，而不是四舍五入😅）
def b_1051():
    from math import sin, cos

    def main():
        r1, p1, r2, p2 = input().split()
        r1 = float(r1)
        p1 = float(p1)
        r2 = float(r2)
        p2 = float(p2)
        a1, b1, a2, b2 = r1 * cos(p1), r1 * sin(p1), r2 * cos(p2), r2 * sin(p2)
        a = a1 * a2 + b1 * b2 * -1
        b = a1 * b2 + a2 * b1
        if b == 0:  # 当a,b为0时，必须输出0，不可以输出0.0(测试点2,3)
            b = 0
        elif a == 0:
            a = 0
        if b >= 0:
            print("{0:.2f}+{1:.2f}i".format(a, b))
        else:
            print("{0:.2f}-{1:.2f}i".format(a, abs(b)))

    main()


# b_1052（更弱智，平台的编译器有问题，本地都可以过，应该是涉及到符号里有转义字符，读不进来，建议百度代码）
def b_1052():
    import sys

    def main():
        di = dict(zip([str(i) for i in range(11)], range(11)))
        s, y, k = input().split('['), input().split('['), input().split('[')
        s[0] = s[0][1:]
        y[0] = y[0][1:]
        k[0] = k[0][1:]
        ls = len(s)
        ly = len(y)
        lk = len(k)
        for i in range(ls-1, -1, -1):
            t = s[i].find(']')
            if t == -1:
                del s[i]
            else:
                s[i] = s[i][:t]
        for i in range(ly-1, -1, -1):
            t = y[i].find(']')
            if t == -1:
                del y[i]
            else:
                y[i] = y[i][:t]
        for i in range(lk-1, -1, -1):
            t = k[i].find(']')
            if t == -1:
                del k[i]
            else:
                k[i] = k[i][:t]
        ls = len(s)
        ly = len(y)
        lk = len(k)
        n = int(input())
        for i in range(n):
            a, b, c, d, e = [di[i] for i in sys.stdin.readline().split()]
            if a > ls or b > ly or c > lk or d > ly or e > ls:
                print("Are you kidding me? @\/@")
            else:
                print(s[a-1]+'('+y[b-1]+k[c-1]+y[d-1]+')'+s[e-1])
    main()


# b_1053
def b_1053():
    import sys

    def main():
        n, e, d = [eval(i) for i in input().split()]
        knkz = 0
        kz = 0
        for i in range(n):
            num = sys.stdin.readline().split()
            dd = num[0]
            num = num[1:]
            count = 0
            for j in num:
                if float(j) < e:
                    count += 1
            if count > int(dd) // 2 and int(dd) > d:
                kz += 1
            elif count > int(dd) // 2:
                knkz += 1
        print('{0:.1f}% {1:.1f}%'.format((knkz/n * 100), (kz/n * 100)))
    main()


# b_1054
def b_1054():
    import re
    def main():
        n = int(input())
        num = input().split()
        sum_ = 0.0
        count = 0
        reg = r"^((\-?)\d+(\.\d{0,2})?)$"
        for i in num:
            if re.search(reg, i):
                t = eval(i)
                if 1000 >= t >= -1000:
                    sum_ += t
                    count += 1
                else:
                    print('ERROR: ' + i + ' is not a legal number')
            else:
                print('ERROR: '+i+' is not a legal number')
        if count == 0:
            print('The average of 0 numbers is Undefined')
        elif count == 1:
            print('The average of 1 number is %.2f'%(sum_/count))
        else:
            print('The average of ' + str(count) + ' numbers is %.2f'%(sum_/count))
    main()


# b_1055
def b_1055():
    import sys
    from math import floor
    class stu():
        def __init__(self, name_, height_):
            self.nm = name_
            self.ht = height_
    def main():
        n, k = input().split()
        n = int(n)
        k = int(k)
        t = floor(n/k)
        m = n % k
        if m != 0:
            ans = [['' for _ in range(t)] for _ in range(k)]
            ans[-1].extend(['' for _ in range(m)])
        else:
            ans = [['' for _ in range(t)] for _ in range(k)]
        stus = []
        for i in range(n):
            name, height = sys.stdin.readline().split()
            st = stu(name, int(height))
            stus.append(st)
        stus.sort(reverse=True, key=lambda x: (-x.ht, x.nm))
        if m == 0:
            for i in range(k):
                center = floor(t/2)+1
                temp = stus[i*t:(i+1)*t]
                temp.reverse()
                f = 0
                for j in temp:
                    ans[i][center+f-1] = j.nm
                    if f == 0:
                        f = -1
                    elif f < 0:
                        f = -f
                    else:
                        f = -f - 1
        else:
            for i in range(k-1):
                center = floor(t / 2) + 1
                temp = stus[i * t:(i + 1) * t]
                temp.reverse()
                f = 0
                for j in temp:
                    ans[i][center + f - 1] = j.nm
                    if f == 0:
                        f = -1
                    elif f < 0:
                        f = -f
                    else:
                        f = -f - 1
            center = floor(len(ans[-1]) / 2) + 1
            temp = stus[(k-1) * t:]
            temp.reverse()
            f = 0
            for j in temp:
                ans[-1][center + f - 1] = j.nm
                if f == 0:
                    f = -1
                elif f < 0:
                    f = -f
                else:
                    f = -f - 1
        ans.reverse()
        for i in ans:
            s = ''
            for j in i:
                s = s + j + ' '
            print(s[:-1])

    main()


# b_1056
def b_1056():
    def main():
        num_dict = dict(zip([str(i) for i in range(10)], range(10)))
        num = [num_dict[i] for i in input().split()]
        n = num[0]
        num = num[1:]
        sum_ = sum(num)
        ans = 11 * (n - 1) * sum_
        print(ans)
    main()


# b_1057
def b_1057():
    def main():
        num_dict = dict(zip(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p'
                     , 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'], range(1, 27)))
        s = input()
        sum_ = 0
        for i in s:
            if i.isalpha():
                sum_ += num_dict[i.lower()]
        if sum_ == 0:
            print('0 0')
        else:
            count_0 = 0
            count_1 = 0
            while True:
                x = sum_ % 2
                if x == 0:
                    count_0 += 1
                else:
                    count_1 += 1
                sum_ = sum_ // 2
                if sum_ == 0:
                    break
            print(count_0, end=' ')
            print(count_1)
    main()


# b_1058
def b_1058():
    import sys
    class tm:
        def __init__(self, mf, gs, zq, xx, id_):
            self.mf = mf
            self.gs = gs
            self.zq = zq
            self.xx = xx
            self.cwqk = 0
            self.id_ = id_

        def add(self):
            self.cwqk += 1

    def main():
        n, m = [int(i) for i in input().split()]
        num_dict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5}
        tk = []
        for i in range(m):
            tm_ = sys.stdin.readline()
            t = tm(num_dict[tm_[0]], num_dict[tm_[2]], num_dict[tm_[4]], tm_[6:-1], i+1)
            tk.append(t)
        for i in range(n):
            student = sys.stdin.readline().split(') (')
            student[0] = student[0][1:]
            student[-1] = student[-1][:-2]
            sum_ = 0
            for j in range(len(student)):
                stu = student[j]
                if num_dict[stu[0]] != tk[j].zq or stu[2:] != tk[j].xx:
                    tk[j].add()
                else:
                    sum_ += tk[j].mf
            print(sum_)
        tk.sort(reverse=True, key=lambda x: (x.cwqk, -x.id_))
        max_ = tk[0].cwqk
        if max_ == 0:
            print('Too simple')
        else:
            res = str(max_)+' '
            for i in tk:
                if i.cwqk == max_:
                    res = res + str(i.id_) + ' '
                else:
                    break
            print(res[:-1])
    main()


# b_1059
def b_1059():
    import sys

    def is_prism(r):
        if r <= 1:
            return False
        t = int(r ** 0.5) + 1
        for i in range(2, t):
            if r % i == 0:
                return False
        return True

    def main():
        n = int(input())
        dic = {}
        ckd = {}
        for i in range(n):
            id_ = sys.stdin.readline()[:-1]
            dic[id_] = i + 1
            ckd[id_] = 0
        k = int(input())
        ids = dic.keys()
        for i in range(k):
            id_ = sys.stdin.readline()[:-1]
            if id_ not in ids:
                print(id_ + ': Are you kidding?')
            else:
                rank = dic[id_]
                if ckd[id_] == 0:
                    if rank == 1:
                        print(id_ + ': Mystery Award')
                    elif is_prism(rank) is True:
                        print(id_ + ': Minion')
                    else:
                        print(id_ + ': Chocolate')
                    ckd[id_] = 1
                else:
                    print(id_ + ': Checked')

    main()


# b_1060（超过和不小于的问题要注意）
def b_1060():
    def main():
        n = int(input())
        num = [int(i) for i in input().split()]
        e = 0
        num.sort()
        for i in range(n):
            if num[n-i-1] > i + 1:
                e = i + 1
        print(e, end='')

    main()


# b_1061
def b_1061():
    import sys

    def main():
        n, m = [int(i) for i in input().split()]
        fs = dict(zip(range(m), [int(i) for i in input().split()]))
        dc = dict(zip(range(m), input().split()))
        for i in range(n):
            x = sys.stdin.readline().split()
            s = 0
            for j in range(m):
                if x[j] == dc[j]:
                    s += fs[j]
            print(s)

    main()


# b_1062
def b_1062():
    def gys(a, b):
        if a < b:
            t = b
            b = a
            a = t
        for i in range(b, 1, -1):
            if a % i == 0 and b % i == 0:
                return i
        return 1

    def gcd(a, b, c):
        t1 = (a * b) // gys(a, b)
        return (t1 * c) // gys(t1, c)

    def main():
        a, b, k = input().split()
        n1, m1 = [int(i) for i in a.split('/')]
        n2, m2 = [int(i) for i in b.split('/')]
        fmm = k
        k = int(k)
        fm = gcd(m1, m2, k)
        fz_1 = n1 * (fm // m1)
        fz_2 = n2 * (fm // m2)
        if fz_2 > fz_1:
            min_ = fz_1
            max_ = fz_2
        else:
            min_ = fz_2
            max_ = fz_1
        res = ''
        for i in range(min_+1, max_):
            if (i * k) % fm == 0:
                sss = i * k // fm
                if gys(sss, k) == 1:
                    fz = str(sss)
                    res = res+fz+'/'+fmm+' '
        print(res[:-1])

    main()


# b_1063
def b_1063():
    import sys
    def main():
        n = int(input())
        r_max = 0
        for i in range(n):
            x, y = [int(i) for i in sys.stdin.readline().split()]
            r = (x ** 2) + (y ** 2)
            if r > r_max:
                r_max = r
        print('%.2f'%(r_max ** 0.5))

    main()


# b_1064
def b_1064():
    def main():
        n = int(input())
        num = input().split()
        num_dict = dict(zip(range(37), [0 for _ in range(37)]))
        n_dict = dict(zip([str(i) for i in range(10)], range(10)))
        for i in range(n):
            sum_ = 0
            for j in num[i]:
                sum_ += n_dict[j]
            num_dict[sum_] += 1
        count = 0
        res = ''
        for i in num_dict.keys():
            if num_dict[i] >= 1:
                count += 1
                res = res + str(i) + ' '
        print(count)
        print(res[:-1])
    main()


# b_1065（又是一个效率题，可以发现set比list效率要高，而且在新集合添加不如从旧集合删除）
def b_1065():
    import sys
    def main():
        n = int(input())
        li = {}
        for i in range(n):
            x, y = sys.stdin.readline().split()
            li[x] = y
        lik = li.keys()
        m = input()
        d = input().split()
        s = set(d)
        for i in s:
            if i in lik and li[i] in s:
                d.remove(i)
                d.remove(li[i])
        d.sort()
        print(len(d))
        if d:
            print(' '.join(d))

    main()


# b_1066
def b_1066():
    import sys
    def main():
        m, n, a, b, h = [int(i) for i in input().split()]
        h = ('00'+str(h))[-3:]
        res = [[h for _ in range(n)] for _ in range(m)]
        for i in range(m):
            hs = [int(i) for i in sys.stdin.readline().split()]
            for j in range(n):
                if not(a <= hs[j] <= b):
                    res[i][j] = ('00'+str(hs[j]))[-3:]
        for i in res:
            if i:
                print(' '.join(i))
    main()


# b_1067
def b_1067():
    import sys
    def main():
        crr, n = input().split(' ')
        n = int(n)
        while True:
            if n == 0:
                print('Account locked')
                break
            it = input()
            if it == '#':
                break
            if it == crr:
                print('Welcome in')
                break
            else:
                n -= 1
                print('Wrong password: ' + it)
    main()


# b_1068（傻逼题目，一边说着周围8个，一边还要考虑边缘的点，这能叫“中”吗）
def b_1068():
    import sys
    def main():
        m, n, tol = [int(i) for i in input().split()]
        dic = {}
        pixs = [[-1 for _ in range(m+2)]]
        for i in range(n):
            pix = [-1]
            pix.extend([int(i) for i in sys.stdin.readline().split()])
            pix.append(-1)
            for j in pix:
                if j in dic.keys():
                    dic[j] = 1
                else:
                    dic[j] = 0
            pixs.append(pix)
        pixs.append([-1 for _ in range(m + 2)])
        res = ''
        for i in range(1, n+1):
            for j in range(1, m+1):
                center = pixs[i][j]
                if dic[center] == 0:
                    a, b, c = pixs[i-1][j-1:j+2]
                    d, f = pixs[i][j-1], pixs[i][j+1]
                    g, h, k = pixs[i+1][j-1:j+2]
                    c_1 = center - tol
                    c_2 = center + tol
                    if c_1 <= a <= c_2 or c_1 <= b <= c_2 or c_1 <= c <= c_2 or c_1 <= d <= c_2 or c_1 <= f <= c_2 or c_1 <= g <= c_2 or c_1 <= h <= c_2 or c_1 <= k <= c_2:
                        pass
                    elif ((not c_1 <= a <= c_2) or a == -1) and \
                            ((not c_1 <= b <= c_2) or b == -1) and \
                            ((not c_1 <= c <= c_2) or c == -1) and \
                            ((not c_1 <= d <= c_2) or d == -1) and \
                            ((not c_1 <= f <= c_2) or f == -1) and \
                            ((not c_1 <= g <= c_2) or g == -1) and \
                            ((not c_1 <= h <= c_2) or h == -1) and \
                            ((not c_1 <= k <= c_2) or k == -1):
                        if res != '':
                            print('Not Unique')
                            return
                        res = '('+str(j)+', '+str(i)+')'+': '+str(center)
        if res == '':
            print('Not Exist')
        else:
            print(res)
    main()


# b_1069（顺移一位的意思居然是从下一位开始重新计算）
def b_1069():
    import sys
    def main():
        m, s, n = [int(i) for i in input().split()]
        zj = []
        for i in range(1, m+1):
            stu = sys.stdin.readline()[:-1]
            if i >= n and (i - n) % s == 0 and stu not in zj:
                print(stu)
                zj.append(stu)
            elif i >= n and (i - n) % s == 0 and stu in zj:
                n += 1
        if len(zj) == 0:
            print('Keep going...')

    main()


# b_1070
def b_1070():
    def main():
        n = int(input())
        num = [int(i) for i in input().split()]
        num.sort()
        length = num[0] / 2 + num[1] / 2
        for i in num[2:]:
            length = length / 2 + i / 2
        print(length//1)
    main()


# b_1071
def b_1071():
    import sys
    def main():
        t_total, k = [int(i) for i in input().split()]
        num_dict = dict(zip([str(i) for i in range(10)], range(10)))
        for i in range(k):
            if t_total == 0:
                print('Game Over.')
                return
            else:
                n1, b, t1, n2 = sys.stdin.readline().split()
                n1, n2 = num_dict[n1], num_dict[n2]
                t = int(t1)
                if t > t_total:
                    print('Not enough tokens.  Total = '+str(t_total)+'.')
                elif (n1 > n2 and b == '0') or (n1 < n2 and b == '1'):
                    t_total += t
                    print('Win '+t1+'!  Total = '+str(t_total)+'.')
                else:
                    t_total -= t
                    print('Lose ' + t1 + '.  Total = ' + str(t_total)+'.')

    main()


# b_1072
def b_1072():
    import sys
    def main():
        n, m = [int(i) for i in input().split()]
        mono = input().split()
        count_sei = 0
        count_mono = 0
        for i in range(n):
            s = sys.stdin.readline().split()
            namae = s[0]
            monos = s[2:]
            kiro = namae+': '
            for j in monos:
                if j in mono:
                    kiro = kiro+j+' '
                    count_mono += 1
            if kiro != (namae + ': '):
                count_sei += 1
                print(kiro[:-1])
        print(count_sei, end=' ')
        print(count_mono)

    main()


# b_1073
def b_1073():
    import sys
    class tm:
        def __init__(self, mf, gs, zq, xx, id_):
            self.mf = mf
            self.gs = gs
            self.zq = zq
            self.xx = xx.split()
            self.id_ = id_
    def main():
        n, m = [int(i) for i in input().split()]
        num_dic = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5}
        tms = []
        cws = {}
        for i in range(1, m+1):
            sis = sys.stdin.readline()
            tm_ = tm(num_dic[sis[0]], num_dic[sis[2]], num_dic[sis[4]], sis[6:-1], i)
            tms.append(tm_)
        for i in range(1, n+1):
            sis = sys.stdin.readline().split(') (')
            sis[0] = sis[0][1:]
            sis[-1] = sis[-1][:-2]
            sum_ = 0
            for j in range(m):
                t = sis[j].split()
                tm_ = tms[j]
                if num_dic[t[0]] < tm_.zq:
                    f = 0.5
                else:
                    f = 1
                for k in t[1:]:
                    if k not in tm_.xx:
                        f = 0
                        s = str(tm_.id_)+'-'+k
                        if s in cws.keys():
                            cws[s] += 1
                        else:
                            cws[s] = 1
                for k in tm_.xx:
                    if k not in t[1:]:
                        s = str(tm_.id_) + '-' + k
                        if s in cws.keys():
                            cws[s] += 1
                        else:
                            cws[s] = 1
                sum_ = sum_ + tm_.mf * f
            print('%.1f'%sum_)
        key = list(cws.keys())
        if len(key) == 0:
            print('Too simple')
        else:
            key.sort(key=lambda x: (-cws[x], x))
            max_ = cws[key[0]]
            for i in key:
                if cws[i] == max_:
                    print(str(cws[i])+' '+i)
                else:
                    break
    main()


# b_1074
def b_1074():
    def main():
        num_dict = dict(zip([str(i) for i in range(10)], range(10)))
        jz_dict = dict(zip([str(i) for i in range(10)], range(10)))
        jz_dict['0'] = 10
        jzb = [jz_dict[i] for i in list(input())]
        n1 = [num_dict[i] for i in list(input())]
        n2 = [num_dict[i] for i in list(input())]
        jzb.reverse()
        n1.reverse()
        n2.reverse()
        c = 0
        l_1 = len(n1)
        l_2 = len(n2)
        if l_1 < l_2:
            s1 = n2
            s2 = n1
            l = l_1
            l_ = l_2
        else:
            s1 = n1
            s2 = n2
            l = l_2
            l_ = l_1
        for i in range(l):
            sum_ = s1[i] + s2[i] + c
            s1[i] = sum_ % jzb[i]
            c = int(sum_ // jzb[i])
        for i in range(l, l_):
            if c == 0:
                break
            sum_ = s1[i] + c
            s1[i] = sum_ % jzb[i]
            c = int(sum_ // jzb[i])
        if c > 0:
            s1.append(c)
        s1.reverse()
        f = False
        for i in s1:
            if f is False and i == 0:
                pass
            else:
                f = True
                print(i, end='')
        if f is False:
            print('0')
        else:
            print('')

    main()


# b_1075（性能题，多用列表少用类）
def b_1075():
    import sys

    def main():
        start, n, k = input().split()
        n = int(n)
        k = int(k)
        chain_data = {}
        chain_typ = {}
        chain_nex = {}
        chain_id = {}
        for i in range(n):
            add, data, nex = sys.stdin.readline().split()
            data = int(data)
            if data < 0:
                tp = 3
            elif 0 <= data <= k:
                tp = 2
            else:
                tp = 1
            chain_data[add] = data
            chain_typ[add] = tp
            chain_nex[add] = nex
        chain_ = [start]
        id_ = 0
        while True:
            s = chain_nex[chain_[-1]]
            if s == '-1':
                chain_id[chain_[-1]] = id_
                break
            else:
                chain_id[chain_[-1]] = id_
                chain_.append(s)
                id_ += 1
        chain_.sort(key=lambda x: (-chain_typ[x], chain_id[x]))
        for i in range(len(chain_)):
            if i != len(chain_) - 1:
                sys.stdout.write(chain_[i]+' '+str(chain_data[chain_[i]])+' '+chain_[i+1]+'\n')
            else:
                sys.stdout.write(chain_[i] + ' ' + str(chain_data[chain_[i]]) + ' -1\n')
    main()


# b_1076
def b_1076():
    import sys

    def main():
        n = int(input())
        s = ''
        for i in range(n):
            ss = sys.stdin.readline().split()
            if 'A-T' in ss:
                s = s + '1'
            elif 'B-T' in ss:
                s = s + '2'
            elif 'C-T' in ss:
                s = s + '3'
            else:
                s = s + '4'
        print(s)
    main()


# b_1077
def b_1077():
    import sys

    def main():
        n, m = input().split()
        n = int(n)
        m = int(m)
        for i in range(n):
            s = sys.stdin.readline().split()
            count = 0
            g1 = 0
            g2 = int(s[0])
            min_ = m
            max_ = 0
            for j in s[1:]:
                nm = int(j)
                if 0 <= nm <= m:
                    count += 1
                    g1 += nm
                    if nm < min_:
                        min_ = nm
                    if nm > max_:
                        max_ = nm
            g1 = (g1 - max_ - min_) / (count - 2)
            print(int((g1 + g2) / 2 + 0.5))

    main()


# b_1078
def b_1078():
    def main():
        tp = input()
        if tp == 'C':
            ss = input()
            x = ss[0]
            count = 1
            ans_ = ''
            for j in range(1, len(ss)):
                if ss[j] == x:
                    count += 1
                else:
                    if count != 1:
                        ans_ = ans_ + str(count)
                    ans_ = ans_ + x
                    x = ss[j]
                    count = 1
            if count != 1:
                ans_ = ans_ + str(count)
            ans_ = ans_ + x
            print(ans_)
        else:
            ss = input()
            count = 0
            ans_ = ''
            for i in range(len(ss)):
                if ss[i].isdigit():
                    count = int(ss[i]) + count * 10
                else:
                    if count == 0:
                        count = 1
                    for j in range(count):
                        ans_ = ans_ + ss[i]
                    count = 0
            print(ans_)
    main()


# b_1079
def b_1079():
    num_dict = {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}
    str_dict = {0:'0',1:'1',2:'2',3:'3',4:'4',5:'5',6:'6',7:'7',8:'8',9:'9'}
    def is_pali(num):
        l = len(num)
        for i in range(int(l/2)):
            if num[i] != num[l-i-1]:
                return False
        return True

    def add(n1, n2):
        c = 0
        ans = ''
        for i in range(len(n1)):
            sum_ = num_dict[n1[i]] + num_dict[n2[i]] + c
            r = str_dict[sum_ % 10]
            c = int(sum_ / 10)
            ans = r + ans
        if c != 0:
            ans = str_dict[c] + ans
        print(n1+' + '+n2+' = '+ans)
        return ans

    def reverse(n):
        ans_ = ''
        for i in n:
            ans_ = i+ans_
        return ans_

    def main():
        n = input()
        if is_pali(n) is True:
            print(n+' is a palindromic number.')
        else:
            for i in range(10):
                n1 = n
                n2 = reverse(n)
                n = add(n1, n2)
                if is_pali(n):
                    print(n+' is a palindromic number.')
                    return
            print('Not found in 10 iterations.')
    main()


# b_1080
def b_1080():
    import sys
    def main():
        p, m, n = [int(i) for i in input().split()]
        score_dict = dict(zip([str(i) for i in range(101)], range(101)))
        gp_dict = {}
        gmid_dict = {}
        gfinal_dict = {}
        zcj_dict = {}
        for i in range(p):
            nm, cj = sys.stdin.readline().split()
            if cj >= '200':
                gp_dict[nm] = cj
        key = set(gp_dict.keys())
        for i in range(m):
            nm, cj = sys.stdin.readline().split()
            if nm in key:
                gmid_dict[nm] = score_dict[cj]
        for i in range(n):
            nm, cj = sys.stdin.readline().split()
            if nm in key:
                gfinal_dict[nm] = score_dict[cj]
        mid_key = set(gmid_dict.keys())
        final_key = set(gfinal_dict.keys())
        for i in key:
            if i not in mid_key:
                gmid_dict[i] = -1
                m = -1
            else:
                m = gmid_dict[i]
            if i not in final_key:
                gfinal_dict[i] = -1
                f = -1
            else:
                f = gfinal_dict[i]
            if m > f:
                sum_ = int((m * 0.4 + f * 0.6) + 0.5)
            else:
                sum_ = f
            if sum_ >= 60:
                zcj_dict[i] = sum_
        k = list(zcj_dict.keys())
        k.sort(key=lambda x: (-zcj_dict[x], x))
        for i in k:
            print(i+' '+gp_dict[i], end=' ')
            print(gmid_dict[i], end=' ')
            print(gfinal_dict[i], end=' ')
            print(zcj_dict[i])
    main()


# b_1081
def b_1081():
    import sys
    import re
    def main():
        n = int(input())
        re1 = r'[^a-zA-Z0-9\.]'
        re2 = r'[0-9]'
        re3 = r'[a-zA-Z]'
        for i in range(n):
            s = sys.stdin.readline()[:-1]
            if len(s) < 6:
                print('Your password is tai duan le.')
            elif re.search(re1, s):
                print('Your password is tai luan le.')
            else:
                if re.search(re3, s):
                    if re.search(re2, s):
                        print('Your password is wan mei.')
                    else:
                        print('Your password needs shu zi.')
                else:
                    print('Your password needs zi mu.')
    main()


# b_1082
def b_1082():
    import sys

    def main():
        n = int(input())
        num_dict = dict(zip([str(i) for i in range(-100, 101)], range(-100, 101)))
        kl = {}
        min_id = ''
        max_id = ''
        for i in range(n):
            s = sys.stdin.readline().split()
            id_ = s[0]
            x = num_dict[s[1]]
            y = num_dict[s[2]]
            kl[id_] = x ** 2 + y ** 2
            if min_id == '':
                max_id = id_
                min_id = id_
            else:
                if kl[id_] < kl[min_id]:
                    min_id = id_
                if kl[id_] > kl[max_id]:
                    max_id = id_
        print(min_id+' '+max_id)
    main()


# b_1083
def b_1083():
    def main():
        n = int(input())
        s = [int(i) for i in input().split()]
        di = {}
        for i in range(1, n+1):
            sub = abs(s[i-1] - i)
            if sub in di.keys():
                di[sub] += 1
            else:
                di[sub] = 1
        k = list(di.keys())
        k.sort(reverse=True)
        for i in k:
            if di[i] != 1:
                print(i, di[i])
    main()


# b_1084（活久见，原来s+=temp比s=s+temp更快）
def b_1084():
    num_dict = dict(zip(range(11), [str(i) for i in range(11)]))

    def chan(s):
        count = 1
        x = s[0]
        ss = ''
        for j in s[1:]:
            if j == x:
                count += 1
            else:
                ss += x + num_dict[count]
                x = j
                count = 1
        return ss + x + num_dict[count]

    def main():
        d, n = input().split()
        n = int(n)
        for _ in range(n - 1):
            d = chan(d)
        print(d)

    main()


# b_1085
def b_1085():
    import sys

    def main():
        n = int(input())
        sco_dict = dict(zip([str(i) for i in range(101)], range(101)))
        xxs_count = {}
        xxs_fs = {}
        for i in range(n):
            zkzh, df, xx = sys.stdin.readline().split()
            xx = xx.lower()
            df = sco_dict[df]
            tp = zkzh[0]
            if xx not in xxs_count.keys():
                xxs_count[xx] = 1
                xxs_fs[xx] = 0
            else:
                xxs_count[xx] += 1
            if tp == 'B':
                t = 1 / 1.5
            elif tp == 'A':
                t = 1
            else:
                t = 1.5
            xxs_fs[xx] += t * df
        ls = list(xxs_count.keys())
        for i in xxs_fs.keys():
            xxs_fs[i] = int(xxs_fs[i])
        ls.sort(key=lambda x: (-xxs_fs[x], xxs_count[x], x))
        max_ = xxs_fs[ls[0]]
        rank = 1
        l = len(ls)
        print(l)
        for i in range(l):
            fs = xxs_fs[ls[i]]
            if fs < max_:
                rank = i+1
                max_ = fs
            print(rank, ls[i], fs, xxs_count[ls[i]])

    main()


# b_1086
def b_1086():
    def main():
        a, b = input().split()
        a = int(a)
        b = int(b)
        s = list(str(a * b))
        s.reverse()
        f = False
        for i in s:
            if i != '0':
                f = True
            if f is True:
                print(i, end='')
        print()

    main()


# b_1087
def b_1087():
    import sys

    def main():
        n = int(input())
        count = 1
        saki = 0
        for i in range(1, n+1):
            t = int(i / 2) + int(i / 3) + int(i / 5)
            if t != saki:
                count += 1
                saki = t
        print(count)
    main()


# b_1088（输出的是甲的能力值……读题失误，卡了一小时妈的）
def b_1088():
    def judge(a, b):
        if a == b:
            return 'Ping'
        elif a > b:
            return 'Gai'
        else:
            return 'Cong'
    def main():
        m, x, y = [int(i) for i in input().split()]
        max_ = 0
        for j in range(99, 9, -1):
            yi = (j % 10) * 10 + int(j / 10)
            if (abs(j - yi) * y) == (x * yi):
                max_ = j
                break
        if max_ == 0:
            print('No Solution')
        else:
            jia = max_
            yi = (jia % 10) * 10 + int(jia / 10)
            bing = yi / y
            print(jia, yi, bing)
            print("%d %s %s %s"%(jia, judge(m, jia), judge(m, yi), judge(m, bing)))
    main()


# b_1089（这题的逻辑有点难理顺，用到了穷举法，不过并没有超时）
def b_1089():
    def main():
        n = int(input())
        A = [0] * (n + 1)  # 用n+1代替n更方便
        for i in range(1, n + 1):
            A[i] = int(input())

        sw = bw = 0
        for i in range(1, n):  # i和j狼
            for j in range(i + 1, n + 1):
                lieh = liew = 0
                for k in range(1, n + 1):
                    # k说的那个人为狼且狼不是假定的i和j，或者k说的那个人是好人且指的是已经假定为狼的i或者j，则k说谎了
                    if A[k] < 0 and -A[k] != i and -A[k] != j or A[k] > 0 and (A[k] == i or A[k] == j):
                        if k != i and k != j:  # k不是狼，则好人说谎
                            lieh += 1
                        else:  # k是狼，则狼人说谎
                            liew += 1
                if liew == 1 and lieh == 1:  # 有且仅有一个好人和一个狼说谎了
                    sw, bw = i, j
                    break
            if sw:
                break
        if sw:
            print("{} {}".format(sw, bw))
        else:
            print("No Solution")
    main()


# b_1090
def b_1090():
    import sys
    def main():
        n, m = input().split()
        n = int(n)
        m = int(m)
        pair = {}
        for i in range(n):
            x, y = sys.stdin.readline().split()
            if x not in pair.keys():
                pair[x] = [y]
            else:
                pair[x].append(y)
            if y not in pair.keys():
                pair[y] = [x]
            else:
                pair[y].append(x)
        for i in range(m):
            s = sys.stdin.readline().split()
            t = int(s[0])
            s = s[1:]
            temp = []
            f = True
            for j in range(t):
                if s[j] in pair.keys():
                    temp.extend(pair[s[j]])
            for j in range(t):
                if s[j] in temp:
                    print('No')
                    f = False
                    break
            if f:
                print('Yes')

    main()


# b_1091（考虑到有可能×N后，在字符串内部存在K这个数，所以不能简单用find函数来处理）
def b_1091():
    def main():
        n = int(input())
        m = input().split()
        s = [int(i) for i in m]
        for i in range(n):
            f = False
            for j in range(1, 10):
                t = str((s[i] ** 2) * j)
                if t.find(m[i]) != -1 and t.split(m[i])[-1] == '':
                    print(j, t)
                    f = True
                    break
            if f is False:
                print('No')
    main()

# b_1092
def b_1092():
    import sys
    def main():
        n, m = input().split()
        n = int(n)
        m = int(m)
        ybs = [0 for _ in range(n)]
        for i in range(m):
            s = sys.stdin.readline().split()
            for j in range(n):
                ybs[j] += int(s[j])
        ybb = {}
        for i in range(n):
            ybb[i] = ybs[i]
        ls = list(ybb.keys())
        ls.sort(key=lambda x: (-ybb[x], x))
        max_ = ybb[ls[0]]
        print(max_)
        ans = ''
        for i in ls:
            if ybb[i] == max_:
                ans += str(i+1) + ' '
        print(ans[:-1])

    main()


# b_1093（能用字符串的地方不要用数组去append，用数组超出400ms，字符串+=只用了77ms)
def b_1093():
    def main():
        a = input()
        b = input()
        t = ''
        for i in a:
            if i not in t:
                t += i
        for i in b:
            if i not in t:
                t += i
        for i in t:
            print(i, end='')
        print()
    main()


# b_1094
def b_1094():
    import math

    def is_prism(s):
        s = int(s)
        if s == 1:
            return False
        if s != 2 and s % 2 == 0:
            return False
        ss = int(math.sqrt(s)) + 1
        for i in range(3, ss, 2):
            if s % i == 0:
                return False
        return True

    def main():
        l, k = input().split()
        l = int(l)
        k = int(k)
        n = input()
        if k > l:
            print('404', end='')
            return
        for i in range(l - k + 1):
            t = n[i:i + k]
            if is_prism(t) is True:
                print(t, end='')
                return
        print('404', end='')

    main()


# b_1095
def b_1095():
    import sys
    def main():
        n, m = [int(i) for i in input().split()]
        A_ls = []
        B_ls = []
        T_ls = []
        zkfs = {}
        kc_rs = {}
        kc_zf = {}
        rq_rs = {}
        for i in range(n):
            zkz, fs = sys.stdin.readline().split()
            jb = zkz[0]
            kc = zkz[1:4]
            rq = zkz[4:10]
            if jb == 'A':
                A_ls.append(zkz)
            elif jb == 'B':
                B_ls.append(zkz)
            else:
                T_ls.append(zkz)
            fs = int(fs)
            zkfs[zkz] = fs
            if kc not in kc_rs.keys():
                kc_rs[kc] = 1
                kc_zf[kc] = fs
            else:
                kc_rs[kc] += 1
                kc_zf[kc] += fs
            if rq not in rq_rs.keys():
                rq_rs[rq] = {kc: 1}
            else:
                if kc not in rq_rs[rq].keys():
                    rq_rs[rq][kc] = 1
                else:
                    rq_rs[rq][kc] += 1
        fa, fb, fc = False, False, False
        for i in range(m):
            lx, zl = sys.stdin.readline().split()
            print('Case ' + str(i+1) + ': ' + lx + ' ' + zl)
            if lx == '1':
                if zl == 'A' and len(A_ls) != 0:
                    if fa is False:
                        A_ls.sort(key=lambda x: (-zkfs[x], x))
                        fa = True
                    for j in A_ls:
                        print(j, zkfs[j])
                elif zl == 'B' and len(B_ls) != 0:
                    if fb is False:
                        B_ls.sort(key=lambda x: (-zkfs[x], x))
                        fb = True
                    for j in B_ls:
                        print(j, zkfs[j])
                elif zl == 'T' and len(T_ls) != 0:
                    if fc is False:
                        T_ls.sort(key=lambda x: (-zkfs[x], x))
                        fc = True
                    for j in T_ls:
                        print(j, zkfs[j])
                else:
                    print('NA')
            elif lx == '2':
                if zl in kc_rs.keys():
                    print(kc_rs[zl], kc_zf[zl])
                else:
                    print('NA')
            elif lx == '3':
                if zl in rq_rs.keys():
                    rqs = rq_rs[zl]
                    ls = list(rqs.keys())
                    ls.sort(key=lambda x: (-rqs[x], x))
                    for j in ls:
                        print(j, rqs[j])
                else:
                    print('NA')
    main()


# b_1096（笨办法，这题主要的问题在于谁除谁，一开始以为是a % sum，其实是sum % a）
def b_1096():
    def ys(x):
        if x == 1:
            return [1]
        else:
            ans = []
            for i in range(1, int(x ** 0.5) + 1):
                if x % i == 0:
                    ans.append(i)
                    if i != int(x / i):
                        ans.append(int(x / i))
            return ans
    def main():
        n = int(input())
        s = [int(i) for i in input().split()]
        for i in range(n):
            sx = ys(s[i])
            l = len(sx)
            if l < 4:
                print('No')
            else:
                f = False
                for j in range(l-3):
                    for k in range(j+1, l-2):
                        for m in range(k+1, l-1):
                            for o in range(m+1, l):
                                if (sx[j]+sx[k]+sx[m]+sx[o]) % s[i] == 0:
                                    f = True
                                    print('Yes')
                                    break
                            if f is True:
                                break
                        if f is True:
                            break
                    if f is True:
                        break
                if f is False:
                    print('No')

    main()


# b_1097
def b_1097():
    import sys
    def main():
        n, k, x = [int(i) for i in input().split()]
        num_dic = dict(zip([str(i) for i in range(101)], range(101)))
        jz = [[x for _ in range(n)] for _ in range(n)]
        ans = ''
        nw = 1
        for i in range(n):
            tp = [num_dic[i] for i in sys.stdin.readline().split()]
            if i % 2 == 1:
                for j in range(n):
                    jz[i][j] = tp[j]
            else:
                for j in range(n-nw):
                    jz[i][j+nw] = tp[j]
                if nw == k:
                    nw = 1
                else:
                    nw += 1
        for i in range(n):
            sum_ = 0
            for j in range(n):
                sum_ += jz[j][i]
            ans += str(sum_)+' '
        print(ans[:-1])
    main()


# b_1098（先排序再去考虑，可以画两条斜线去形象地代替排好序的上界与下界）
def b_1098():
    def main():
        n = int(input())
        dings = [int(i) for i in input().split()]
        dis = [int(i) for i in input().split()]
        dings.sort()
        dis.sort()
        if dis[-1] < dings[0]:
            print('Yes', dings[0] - dis[-1])
        else:
            print('No', dis[-1] - dings[0] + 1)

    main()


# b_1099（要考虑n-6会不会小于1的情况出现，要加以限制）
def b_1099():
    def is_prime(x):
        if x == 1:
            return False
        if x % 2 == 0 and x != 2:
            return False
        for i in range(3, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True
    def main():
        n = int(input())
        if is_prime(n):
            if n > 7 and is_prime(n-6):
                print('Yes')
                print(n-6)
                return
            elif is_prime(n+6):
                print('Yes')
                print(n+6)
                return
        print('No')
        if n % 2 == 0:
            i = n + 1
        else:
            i = n + 2
        while True:
            if is_prime(i) and ((i > 7 and is_prime(i - 6)) or is_prime(i + 6)):
                print(i)
                return
            else:
                i = i + 2
    main()


# b_1100（纯性能题，用dict以及set(dic.keys())搭配来做，瞬间从800ms超时变到113ms）
def b_1100():
    import sys

    def main():
        n = int(input())
        xy = {}
        for i in range(n):
            xy[sys.stdin.readline()[:-1]] = 1
        m = int(input())
        count = 0
        ma = ''
        mas = ''
        stt = set(xy.keys())
        for i in range(m):
            x = sys.stdin.readline()[:-1]
            t = x in stt
            xs = x[6:14]
            if t is True:
                count += 1
            elif count > 0:
                continue
            if ma == '':
                ma = x
                mas = ma[6:14]
            elif count == 0 and xs < mas:
                ma = x
                mas = xs
            elif count != 0 and t is True and xs < mas:
                ma = x
                mas = xs
        print(count)
        sys.stdout.write(ma + '\n')

    main()


# b_1101
def b_1101():
    def main():
        a, d = input().split()
        d = int(d)
        b = a[-d:] + a[:-d]
        a = int(a)
        b = int(b)
        print('%.2f'%(b / a))
    main()


# b_1102
def b_1102():
    import sys

    def main():
        n = int(input())
        xlid = ''
        xl = 0
        xseid = ''
        xse = 0
        for i in range(n):
            id_, dj_, gmrs_ = sys.stdin.readline().split()
            dj_ = int(dj_)
            gmrs_ = int(gmrs_)
            if xlid == '':
                xlid = id_
                xseid = id_
                xl = gmrs_
                xse = dj_ * gmrs_
            else:
                if gmrs_ > xl:
                    xlid = id_
                    xl = gmrs_
                if dj_ * gmrs_ > xse:
                    xseid = id_
                    xse = dj_ * gmrs_
        print(xlid, xl)
        print(xseid, xse)
    main()


# b_1103
def b_1103():
    def check(t):
        ts = int(t ** 0.5)
        if ts * ts != t:
            return 0
        else:
            return ts

    def main():
        m, n = input().split()
        m = int(m)
        n = int(n)
        f = False
        if m == 1:
            m = 2
        for i in range(m, n+1):
            a = i ** 3
            b = (i - 1) ** 3
            c = check(a - b)  # 确保这俩减完是平方数
            if c != 0:
                d = check(2 * c - 1)  # 根据b的公式可知为2(b²-b)+1的格式
                if d % 2 == 1:
                    print(i, int((d+1)/2))
                    f = True
        if f is False:
            print('No Solution')

    main()


# b_1104（这道题，Python是无解的，只能拿到15分，所以看看思路就行，要AC还是得靠C++）
def b_1104():
    import sys
    def is_prime(x):
        if x <= 2:
            return False
        if x % 2 == 0:
            return False
        for i in range(3, int(x ** 0.5) + 1, 2):
            if x % i == 0:
                return False
        return True
    def gcd(x, y):
        if x % y == 0:
            return y
        else:
            return gcd(y, x % y)
    def gys(x, y):
        max_ = gcd(x, y)
        if is_prime(max_) is True:
            return True
        else:
            return False

    def main():
        n = int(input())
        num_dict = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, '10': 10, '11': 11, '12': 12, '13': 13, '14': 14, '15': 15, '16': 16, '17': 17, '18': 18, '19': 19, '20': 20, '21': 21, '22': 22, '23': 23, '24': 24, '25': 25, '26': 26, '27': 27, '28': 28, '29': 29, '30': 30, '31': 31, '32': 32, '33': 33, '34': 34, '35': 35, '36': 36, '37': 37, '38': 38, '39': 39, '40': 40, '41': 41, '42': 42, '43': 43, '44': 44, '45': 45, '46': 46, '47': 47, '48': 48, '49': 49, '50': 50, '51': 51, '52': 52, '53': 53, '54': 54, '55': 55, '56': 56, '57': 57, '58': 58, '59': 59, '60': 60, '61': 61, '62': 62, '63': 63, '64': 64, '65': 65, '66': 66, '67': 67, '68': 68, '69': 69, '70': 70, '71': 71, '72': 72, '73': 73, '74': 74, '75': 75, '76': 76, '77': 77, '78': 78, '79': 79, '80': 80, '81': 81, '82': 82, '83': 83, '84': 84, '85': 85, '86': 86, '87': 87, '88': 88, '89': 89, '90': 90}
        str_dict = {0: '0', 1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9', 10: '10', 11: '11', 12: '12', 13: '13', 14: '14', 15: '15', 16: '16', 17: '17', 18: '18', 19: '19', 20: '20', 21: '21', 22: '22', 23: '23', 24: '24', 25: '25', 26: '26', 27: '27', 28: '28', 29: '29', 30: '30', 31: '31', 32: '32', 33: '33', 34: '34', 35: '35', 36: '36', 37: '37', 38: '38', 39: '39', 40: '40', 41: '41', 42: '42', 43: '43', 44: '44', 45: '45', 46: '46', 47: '47', 48: '48', 49: '49', 50: '50', 51: '51', 52: '52', 53: '53', 54: '54', 55: '55', 56: '56', 57: '57', 58: '58', 59: '59', 60: '60', 61: '61', 62: '62', 63: '63', 64: '64', 65: '65', 66: '66', 67: '67', 68: '68', 69: '69', 70: '70', 71: '71', 72: '72', 73: '73', 74: '74', 75: '75', 76: '76', 77: '77', 78: '78', 79: '79', 80: '80', 81: '81'}
        for i in range(n):
            k, m = sys.stdin.readline().split()
            k = num_dict[k]
            m = num_dict[m]
            print('Case', i+1)
            if k * 9 < m or k <= 3 or is_prime(m):
                print('No Solution')
                continue
            k_max = 10 ** (k - 2)
            k_min = 10 ** (k - 3)
            ans_dic = {}
            ans = ''
            for a in range(k_min, k_max):
                # 这一步将非99结尾的都筛掉了，速度提升了40倍
                b = a * 100 + 99
                a_1 = b + 1
                b = str(b)
                mm = sum([num_dict[j] for j in b])
                if mm == m:
                    nn = sum([num_dict[j] for j in str(a_1)])
                    if mm > nn:
                        dd = gys(mm, nn)
                    else:
                        dd = gys(nn, mm)
                    if dd is True:
                        if nn in set(ans_dic.keys()):
                            ans_dic[nn] += str_dict[nn] + ' ' + b + '\n'
                        else:
                            ans_dic[nn] = str_dict[nn] + ' ' + b + '\n'
            ls = list(ans_dic.keys())
            if len(ls) == 0:
                print('No Solution')
            else:
                ls.sort()
                for j in set(ls):
                    print(ans_dic[j][:-1])
    main()


# b_1105（耗时最少的版本，能过4个测试点，测试点5虽然不超时，但是会内存超限，无法AC）
def b_1105():
    import sys
    def main():
        start_a, start_b, n = input().split()
        n = int(n)
        data_dic = {}
        nex_dic = {}
        for i in range(n):
            add, data, nex = sys.stdin.readline().split()
            data_dic[add] = data
            nex_dic[add] = nex
            del add
            del data
            del nex
        chain_a = start_a
        chain_b = start_b
        nxt = start_a
        while True:
            nxt = nex_dic[nxt]
            if nxt == '-1':
                break
            chain_a += nxt
        nxt = start_b
        while True:
            nxt = nex_dic[nxt]
            if nxt == '-1':
                break
            chain_b += nxt
        del nex_dic
        l_a = len(chain_a)
        l_b = len(chain_b)
        l = int((l_a + l_b) / 5)
        chain_final = ''
        t_10 = -10
        t_11 = 0
        t_5 = 5
        if l_a > l_b:
            f = False
            while True:
                t_10 += 10
                t_11 = t_10 + 10
                t_5 -= 5
                if l_b <= 5 and f is False:
                    chain_final += chain_a[t_10:t_11]
                    if t_5 != 0:
                        chain_final += chain_b[:t_5]
                    else:
                        chain_final += chain_b
                    f = True
                elif f is True:
                    chain_final += chain_a[t_10:]
                    break
                else:
                    chain_final += chain_a[t_10:t_11]
                    t_5 -= 5
                    chain_final += chain_b[t_5:]
                    t_5 += 5
                    l_a -= 10
                    l_b -= 5
        else:
            f = False
            while True:
                t_10 += 10
                t_11 = t_10 + 10
                t_5 -= 5
                if l_a <= 5 and f is False:
                    chain_final += chain_b[t_10:t_11]
                    if t_5 != 0:
                        chain_final += chain_a[:t_5]
                    else:
                        chain_final += chain_a
                    f = True
                elif f is True:
                    chain_final += chain_b[t_10:]
                    break
                else:
                    chain_final += chain_b[t_10:t_11]
                    t_5 -= 5
                    chain_final += chain_a[t_5:]
                    t_5 += 5
                    l_a -= 5
                    l_b -= 10
        del chain_a
        del chain_b
        for i in range(l - 1):
            t = i * 5
            tt = t + 5
            ttt = tt + 5
            add = chain_final[t:tt]
            print(add, data_dic[add], chain_final[tt:ttt])
        add = chain_final[-5:]
        print(add, data_dic[add], '-1')

    main()


# b_1106
    def main():
        n = int(input())
        num_dic = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
        str_dict = {0: '0', 1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9'}
        s = '2019'
        for i in range(n-4):
            sum_ = num_dic[s[i]]+num_dic[s[i+1]]+num_dic[s[i+2]]+num_dic[s[i+3]]
            sum_ = sum_ % 10
            s += str_dict[sum_]
        print(s[:n])
    main()


# b_1107
def b_1107():
    import sys
    def main():
        n, m = input().split()
        n = int(n)
        max_ = 0
        ans = ''
        for i in range(n):
            x = [int(i) for i in sys.stdin.readline().split()]
            mm = max(x)
            ans += str(mm)+' '
            if mm > max_:
                max_ = mm
        print(ans[:-1])
        print(max_)
    main()


# b_1108
def b_1108():
    def main():
        s_dict = {'S': 0, 't': 0, 'r': 0, 'i': 0, 'n': 0, 'g': 0}
        s = input()
        key = s_dict.keys()
        for i in s:
            if i in key:
                s_dict[i] += 1
        while True:
            f = False
            for i in key:
                if s_dict[i] != 0:
                    print(i, end='')
                    s_dict[i] -= 1
                    f = True
            if f is False:
                print('')
                break
    main()


# b_1109
def b_1109():
    import sys
    def main():
        dxzm = [i for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ']
        id_ = dict(zip(range(26), dxzm))
        alpha = dict(zip(dxzm, [[] for _ in range(26)]))
        for i in range(26):
            l_1 = sys.stdin.readline()[:-1]
            l_2 = sys.stdin.readline()[:-1]
            l_3 = sys.stdin.readline()[:-1]
            l_4 = sys.stdin.readline()[:-1]
            l_5 = sys.stdin.readline()[:-1]
            l_6 = sys.stdin.readline()[:-1]
            l_7 = sys.stdin.readline()[:-1]
            l = [l_1, l_2, l_3, l_4, l_5, l_6, l_7]
            alpha[id_[i]] = l
        s = input()
        end = 0
        l_ = len(s)
        word = ''
        s1 = ''
        while True:
            if end == l_-1:
                if s[end] in dxzm:
                    word += s[end]
                break
            if s[end] in dxzm:
                word += s[end]
                end += 1
            elif word != '':
                for i in range(7):
                    for j in word:
                        s1 += alpha[j][i]+' '
                    s1 = s1[:-1] + '\n'
                s1 += '\n'
                end += 1
                word = ''
            else:
                end += 1
        if word != '':
            for i in range(7):
                for j in word:
                    s1 += alpha[j][i] + ' '
                s1 = s1[:-1] + '\n'
        if s1[-2] == '\n':
            print(s1[:-2])
        else:
            print(s1[:-1])
    main()


# b_1110（明明没有任何问题，但是就是最后一个测试点非零返回，Debug出来是输出那部分出现的问题，但是我无法改正，怀疑是编译器的锅）
def b_1110():
    import sys
    def main():
        start, n, k = input().split()
        n = int(n)
        k = int(k)
        if n <= 0 or k <= 0:
            return
        data_dic = {}
        nxt_dic = {}
        for i in range(n):
            add, data, nxt = sys.stdin.readline().split()
            data_dic[add] = data
            nxt_dic[add] = nxt
        chain_origin = start
        nxt = start
        count = 0
        while True:
            if count % k == k-1:
                chain_origin += ' '
            nxt = nxt_dic[nxt]
            if nxt == '-1':
                break
            chain_origin += nxt
            count += 1
        ls = chain_origin.split(' ')
        ls.reverse()
        chain_after = ''
        for i in ls:
            chain_after += i
        for i in range(n-1):
            x = chain_after[i*5:(i+1)*5]
            y = chain_after[(i+1)*5:(i+2)*5]
            print(x, data_dic[x], y)
        x = chain_after[-5:]
        print(x, data_dic[x], '-1')
    main()